// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

use std::cmp::Ordering;
use std::fmt::Debug;
use std::ptr;

// A doubly linked list entry.
#[derive(Debug)]
struct ListEntry<T> {
    data: T,
    prev: *mut ListEntry<T>,
    next: *mut ListEntry<T>,
}

impl<T> ListEntry<T> {
    fn new(data: T) -> Self {
        ListEntry {
            data,
            prev: ptr::null_mut(),
            next: ptr::null_mut(),
        }
    }
}

// A doubly linked list.
pub struct List<T> {
    head: *mut ListEntry<T>,
    tail: *mut ListEntry<T>,
    length: usize,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List {
            head: ptr::null_mut(),
            tail: ptr::null_mut(),
            length: 0,
        }
    }

    pub fn append(&mut self, data: T) -> bool {
        let new_entry = Box::into_raw(Box::new(ListEntry::new(data)));
        if self.tail.is_null() {
            self.head = new_entry;
            self.tail = new_entry;
        } else {
            unsafe {
                (*self.tail).next = new_entry;
                (*new_entry).prev = self.tail;
                self.tail = new_entry;
            }
        }
        self.length += 1;
        true
    }

    pub fn prepend(&mut self, data: T) -> bool {
        let new_entry = Box::into_raw(Box::new(ListEntry::new(data)));
        if self.head.is_null() {
            self.head = new_entry;
            self.tail = new_entry;
        } else {
            unsafe {
                (*self.head).prev = new_entry;
                (*new_entry).next = self.head;
                self.head = new_entry;
            }
        }
        self.length += 1;
        true
    }

    pub fn length(&self) -> usize {
        self.length
    }

    pub fn nth_data(&self, index: usize) -> Option<&T> {
        let mut rover = self.head;
        for _ in 0..index {
            if rover.is_null() {
                return None;
            }
            unsafe {
                rover = (*rover).next;
            }
        }
        if rover.is_null() {
            None
        } else {
            unsafe { Some(&(*rover).data) }
        }
    }

    pub fn free(&mut self) {
        let mut rover = self.head;
        while !rover.is_null() {
            let next = unsafe { (*rover).next };
            unsafe {
                drop(Box::from_raw(rover));
            }
            rover = next;
        }
        self.head = ptr::null_mut();
        self.tail = ptr::null_mut();
        self.length = 0;
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        self.free();
    }
}

// Test suite for the doubly linked list.
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_list_append() {
        let mut list = List::new();
        assert!(list.append(50));
        assert!(list.append(0));
        assert!(list.append(0));
        assert!(list.append(0));
        assert_eq!(list.length(), 4);
        assert_eq!(list.nth_data(0), Some(&50));
        assert_eq!(list.nth_data(1), Some(&0));
        assert_eq!(list.nth_data(2), Some(&0));
        assert_eq!(list.nth_data(3), Some(&0));
    }

    #[test]
    fn test_list_prepend() {
        let mut list = List::new();
        assert!(list.prepend(50));
        assert!(list.prepend(0));
        assert!(list.prepend(0));
        assert!(list.prepend(0));
        assert_eq!(list.length(), 4);
        assert_eq!(list.nth_data(0), Some(&0));
        assert_eq!(list.nth_data(1), Some(&0));
        assert_eq!(list.nth_data(2), Some(&0));
        assert_eq!(list.nth_data(3), Some(&50));
    }

    #[test]
    fn test_list_free() {
        let mut list = List::new();
        list.append(50);
        list.append(0);
        list.free();
        assert_eq!(list.length(), 0);
    }

    #[test]
    fn test_list_next() {
        let mut list = List::new();
        list.append(50);
        list.append(0);
        list.append(0);
        list.append(0);
        let mut rover = list.head;
        unsafe {
            assert_eq!((*rover).data, 50);
            rover = (*rover).next;
            assert_eq!((*rover).data, 0);
            rover = (*rover).next;
            assert_eq!((*rover).data, 0);
            rover = (*rover).next;
            assert_eq!((*rover).data, 0);
            rover = (*rover).next;
            assert!(rover.is_null());
        }
    }

    #[test]
    fn test_list_nth_entry() {
        let mut list = List::new();
        list.append(50);
        list.append(0);
        list.append(0);
        list.append(0);
        assert_eq!(list.nth_data(0), Some(&50));
        assert_eq!(list.nth_data(1), Some(&0));
        assert_eq!(list.nth_data(2), Some(&0));
        assert_eq!(list.nth_data(3), Some(&0));
        assert_eq!(list.nth_data(4), None);
        assert_eq!(list.nth_data(400), None);
    }

    #[test]
    fn test_list_length() {
        let mut list = List::new();
        list.append(50);
        list.append(0);
        list.append(0);
        list.append(0);
        assert_eq!(list.length(), 4);
        list.prepend(50);
        assert_eq!(list.length(), 5);
    }
}
